1. Field of the Invention
This invention has as its object a circuit to perform a linear transformation on a digital signal composed of N digital samples, where N is a whole number. The invention is particularly applicable in the processing of digital signals, for example picture or speech signals, for the coding of these signals before they are transmitted on a transmission line.
2. Discussion of Background
In these application, various types of linear transformation are used, such as for example the discrete Fourier transform, the discrete cosine transform, the discrete sine transform, the discrete Hadamard transform, or the like. These transforms are called "discrete" with reference to the digital characteristic of the processed signal.
The linear transformation applied to a digital signal of N samples is represented traditionally by a graph in which the branches represent a multiplication operation and the nodes an addition or subtraction operation.
Such graphs are described, for a discrete cosine transformation, in the following documents:
French patent application No. 85 15649 filed on Oct. 22, 1985, now publication No. 2,589,020.
"A fast computational algorithm for the discrete cosine transform" of W. H. CHEN et al, IEEE Transactions on Communication, vol. COM-25, No. 9, Sept. 1977, pages 1004 to 009,
A high FDCT processor for real-time processing of NTSC color TV signal" of A. JALALI et al, IEEE Transactions on Electromagnetic Compatibility, vol. EMC-24, No. 2, May 1982, pages 278 to 286,
U.S. Pat. No. 4,385,363.
The practical embodiment of a circuit based on a linear transformation graph runs into two main problems, which are, on the one hand, the volume of the computations to be performed and, on the other hand, a flood of very complicated data between the various stages of the graph, because of the complexity of this graph.
Numerous works have already been done on simplifying the transformation algorithms, i.e., on the graphs, by reducing the number of multiplication operations to reduce the flow of data.
Actually, this reduction is desired because the multipliers are the costly elements of the circuit, both as regards their price, and their surface or their consumption. The number of multipliers is therefore reduced to a minimum by assigning to each multiplier the computations of several branches of the graph, so as to obtain a maximum rate of use of each of these multipliers.
Two types of circuit for performing a linear transformation, particularly a discrete cosine transformation or a discrete Fourier transformation are known.
A first known architecture consists in using a large number of signal processing microprocessors working in parallel. The known architecture consists in using standard multipliers and adders connected to one another. This circuit is described particularly in U.S. Pat. No. 4,385,363 already cited. For these two architectures, it involves an assembly of integrated circuits.
It has already also been proposed to make a linear transformation circuit in the form of a specific integrated circuit comprising several multipliers working in parallel. These multipliers are not specialized, i.e., between each other they can multiply any two numbers.
Circuits of the prior art exhibit the drawback of using only standard multiplying and adders, which does not make it possible to take into account the specific characteristics of the graph of the transformation that it is desired to achieve. This deviation between the architecture of the linear transformation circuits and the structure of the algorithm represented by the graph does not make it possible to optimize the processing.